package bytedance

/**
 * 70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
 */
fun climbStairs(n: Int): Int {
    if (n <= 1) return 1;
    if (n == 2) return 2;
    val dp = Array(n) { 0 }
    dp[0] = 1
    dp[1] = 2
    for (i in 2 until n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n-1];
}
class Main{
    companion object{
        @JvmStatic
        public fun main(args:Array<String>){
            println(climbStairs(1));
            println(climbStairs(2));
            println(climbStairs(3));
            println(climbStairs(4));
        }
    }
}